Transmission of digital data over great distances is currently accomplished by digital networks, such as the familiar “internet”. In that network, digital data propagates over the network as individual packets or, as variously termed, cells of serial binary data. The cell includes at least the information that the sender desires to have delivered to the recipient and the address of the intended recipient station or computer. The network is designed to use the destination address to route the cell over the digital network, that is, permits the packet or cell to be self-routing.
The digital network typically requires a number of component electronic devices, also referred to as switching networks or switches that assist the migration or propagation of the cells through the transmission network. One of those component electronic devices is known as the Batcher-banyan network. The Batcher-banyan network is a class of multi-stage switching network that permits data cells arriving at any one of the multiple inputs to the network to propagate to any of the multiple outputs of the network. That network is formed of a combination of a Banyan switching network and a Batcher sorting network.
The Banyan switching network is described, for one, in an article by L. R. Goke and G. J. Lipovski, entitled Banyan Networks for Partitioning Multi-Processing Systems, Proceedings 1st Annual Computer Architecture Conference, pp 21-28, December 1973. The Banyan switching network or switch possesses the capability of transferring multiple cell inputs simultaneously to multiple outputs, but with an inherent limitation or problem. That transfer is low in efficiency due to the possibility of a cell collision arising in the inner part or output lines of the switch, which causes internal blocking. That is, when sending several cells from different inputs to propagate to different outputs, two or more of those cells may well attempt to take the same circuit link through a part of the network taken by another of the inputted cells. That action produces a cell “collision”. As a consequence, one or the other of the colliding cells needs to be dropped or delayed, and the dropped or delayed cell would need to be re-presented to the network later. That cell action (and reaction) lowers the efficiency of cell transfer.
However, the banyan network is internally non-blocking if two conditions are met: (1) All active cells are presented to the network sorted in order by destination and (2) no inactive cells (e.g. cells that contain no data so that the data section is a string of “0's”) are positioned between the active cells. The first condition is satisfied by pre-pending the banyan network with the Batcher sorting network. The function of the Batcher sorting network is described in a article by the inventor of the network, Mr. K, Batcher, in an article entitled “Sorting Networks and their Applications”, AIFPS Spring Joint Computer Conference Proceedings, Volume 32, pp 307-314, 1968. To satisfy the second condition a so-called concentrator network is placed between the Batcher and banyan stages.
When several of the input cells have the same destination address and seek to propagate to the same output, an event termed output contention, it is necessary to detect and resolve that impossible situation. Resolution of the contention is accomplished by including a trap network or, as variously termed, trap in between the Batcher and concentrator stages of the Batcher-Banyan network. The present invention encompasses an improvement to the Batcher-Banyan network, particularly to the switching core to the network, to a novel routing circuit employed in that network and to a novel trap network.
One approach to increasing the information carrying capacity of a digital transmission network is by increasing the transmission speed at which the data cells move over the network. The Batcher-Banyan network bit serial routing and switching network architectures that utilize such routing were successfully implemented previously in conventional voltage-state semiconductor logic e.g., Asynchronous Mode Switches (“ATM”) switches. That semiconductor logic operates at hundreds of megahertz to several gigahertz data processing clock frequency as compared to the greater data processing speeds of operation of the newly evolving superconductor device technology, to which the present invention is directed, at link rates of 10 to 40 to 60 gbps. Superconductor devices, herein referred to as SFQ or RSFQ devices, are known that emulate various kinds of semiconductor logic devices, such as flip-flops and other gates, but operate at significantly faster speeds and with much lower power consumption.
SFQ is an acronym for single flux quantum. That term is used herein interchangeably with RSFQ, which stands for rapid single flux quantum, an alternative phrase used by some who prefer to emphasis the high speed of superconductor devices. The SFQ (and RSFQ) designation indicates that the particular device that follows the designation incorporates one or more Josephson Junctions as an active element or elements and relies on quantum-mechanical phenomena called “magnetic flux quantization”. SFQ devices process information by counting individual magnetic flux quanta, unlike other families of Josephson Junction logic, the so-called “voltage states” or “latching” logic. As is known, for operation SFQ devices must be held in an environment that maintained at cryogenic temperatures; and those devices must be supplied with appropriate DC bias currents. As an advantage, the present invention employs SFQ devices configured to function as a Batcher-Banyan network to enable significant enhancement in the speed with which data cells are routed. A secondary advantage is that the power dissipated in the switching core is significantly reduced relative to one formed of conventional semiconductor logic.
Since the semiconductor type Batcher-Banyan network includes a two-bit serial sorter and a trap, an SFQ Batcher-Banyan network must of necessity include counterpart SFQ devices to accomplish the sorter and trap functions. As corollary inventions, the present invention provides a new configuration in SFQ devices that provides an SFQ bit-sorter and an SFQ trap.
Accordingly, a principal object of the present invention is to provide true packet switching at optical speeds of 40 to 60 Gbps and beyond.
Another object of the invention is to miniaturize a Batcher Banyan superconductor network switching core, and fit that network switching core in a single cryo-multi-chip module.
A further object of the invention is to create an SFQ two-bit serial sorter that is capable of routing packets of SFQ pulses, and is able to support an arbitrary number of priority bits.
A still further object of the invention is to provide an SFQ trap that is able to compare addresses of two separate SFQ cells and, when the cell addresses are identical, blocks transmission of the cell with lowest priority.